package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
 *
 * 25. K 个一组翻转链表
 *
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * @author hanjuntao
 * @date 2025/8/4 0004
 */
public class L_25_reverse_nodes_in_k_group {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode result = reverseKGroup(node1, 3);
        ListNode.print(result);
    }

    /**
     * 思路：
     *
     * 该题实际上是在给定区间反转链表的扩展，有多个区间可以反转链表
     *
     *
     * 在某个区间内进行反转的实现参考：L_92_ReverseBetween.java
     *
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        int count = 0;
        int index = 0;
        boolean reversed = false;

        ListNode curr = head;
        while (curr != null) {
            index++;
            count++;

            ListNode next = curr.next;

            if (count == k) {
                int start = index - k + 1;
                ListNode listNode = reverseBetween(head, start, index);

                if (!reversed) {
                    head = listNode;
                    reversed = true;
                }

                count = 0;
            }

            curr = next;
        }

        return head;
    }


    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return null;
        }

        if (right < left) {
            return head;
        }

        // 选中链表头结点的上一个节点
        ListNode lastDealHead = null;
        // 选中链表头结点
        ListNode dealHead = null;
        // 选中链表尾结点
        ListNode dealTail = null;
        // 选中链表尾结点下一个节点
        ListNode nextDealTail = null;

        ListNode curr = head;
        int begin = 1;

        while (curr != null) {
            if (begin == left - 1) {
                lastDealHead = curr;
            }

            if (begin == left) {
                dealHead = curr;
            }

            if (begin == right) {
                dealTail = curr;

                // 可能是空
                nextDealTail = curr.next;
            }

            begin++;
            curr = curr.next;
        }

        if (dealTail != null) {
            dealTail.next = null;
        }

        ListNode newHead = revereList(null, dealHead);

        if (lastDealHead == null) {
            dealHead.next = nextDealTail;
            return newHead;
        } else {
            lastDealHead.next = newHead;
            dealHead.next = nextDealTail;
            return head;
        }
    }

    private static ListNode revereList(ListNode prev, ListNode dealHead) {
        if (dealHead == null) {
            return prev;
        }

        ListNode next = dealHead.next;
        dealHead.next = prev;
        return revereList(dealHead, next);
    }

}
